package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-11 16:38
 */
public class Q322 {
//    public int coinChange(int[] coins, int amount) {
//        if(amount == 0){
//            return 0;
//        }
//
//        int[] dp = new int[amount + 1];
//        for (int i = 1; i < dp.length; i++) {
//            dp[i] = Integer.MAX_VALUE;
//            for (int j = 0; j < coins.length; j++) {
//                if(i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE){
//                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
//                }
//            }
//        }
//
//        if (dp[amount] == Integer.MAX_VALUE) {
//            return -1;
//        } else {
//            return dp[amount];
//        }
//    }

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        } else {
            return dp[amount];
        }
    }
}
